//
// Description: 1743. 从相邻元素对还原数组
// Created by Loading on 2021/7/25.
//

#include <bits/stdc++.h>

using namespace std;

vector<int> restoreArray(vector<vector<int>> &adjacentPairs) {
    // 统计相邻元素集合
    unordered_map<int, vector<int>> statistics;
    for (auto &v : adjacentPairs) {
        statistics[v[0]].emplace_back(v[1]);
        statistics[v[1]].emplace_back(v[0]);
    }

    // 寻找只出现一次的元素，一定是端点
    int start = 0, start_next = 0;
    for (auto &[k, v] : statistics) {
        if (v.size() == 1) {
            start = k;
            start_next = v[0];
            break;
        }
    }

    // 还原整个数组
    vector<int> res;
    res.emplace_back(start);
    res.emplace_back(start_next);
    for (int i = 2; i < adjacentPairs.size() + 1; ++i) {
        auto &v = statistics[res[i - 1]];
        res.emplace_back(v[0] == res[i - 2] ? v[1] : v[0]);
    }

    return res;
}

int main() {
    vector<vector<int>> adjacentPairs = {{2, 1},
                                         {3, 4},
                                         {3, 2}};
    vector<int> res = restoreArray(adjacentPairs);
    for (auto &x : res) {
        cout << x << " ";
    }
    cout << endl;
}